package treeedit;

import java.util.Hashtable;
import java.util.Map;

/**
 * This class implements the Binary Branch Filter algorithm. It takes trees as
 * inputs, normalizes them and returns the distance between them.
 */
public class BBFAlgorithm {
	public final static int threshold = 20;

	public BBFAlgorithm() {
	}

	/**
	 * If the lower bound (BBF) is lower than the threshold, calculate TED.
	 * 
	 * @param tree1
	 *            Tree to find distance from
	 * @param tree2
	 *            Tree to find distance to
	 * @return distance as an integer number. If no distance was calculated due
	 *         to above-threshold BBF value, return Integer.MAX_VALUE.
	 */
	public static int getDistance(Tree tree1, Tree tree2) {
		if (getLowerBound(tree1, tree2) <= BBFAlgorithm.threshold) {
			return TedAlgorithm.getDistance(tree1, tree2);
		}
		return Integer.MAX_VALUE;
	}

	public static int getDistance(Tree tree1, Tree tree2, double threshold) {
		if (getLowerBound(tree1, tree2) <= threshold) {
			return TedAlgorithm.getDistance(tree1, tree2);
		}
		return Integer.MAX_VALUE;
	}

	/**
	 * Wrapper method for {@link #getLowerBound(NBTree, NBTree)} method.
	 * 
	 * @return result of call of the {@link #getLowerBound(NBTree, NBTree)}
	 *         method.
	 */
	private static int getLowerBound(Tree tree1, Tree tree2) {
		return getLowerBound(new NBTree(tree1), new NBTree(tree2));
	}

	/**
	 * Returns the lower bound of the distance between between two normalized
	 * input trees.
	 */
	private static int getLowerBound(NBTree T1, NBTree T2) {
		Map<String, Integer> BBV1 = new Hashtable<String, Integer>();
		Map<String, Integer> BBV2 = new Hashtable<String, Integer>();
		computeVector(BBV1, T1);
		computeVector(BBV2, T2);

		// Assume the key that in BBV2 but not in BBV1, has 0 value.
		for (String key : BBV2.keySet()) {
			if (!BBV1.containsKey(key))
				BBV1.put(key, 0);
		}

		// Compute the differences
		int distance = 0;
		for (String key : BBV1.keySet()) {
			int v1 = BBV1.get(key);
			int v2 = BBV2.containsKey(key) ? BBV2.get(key) : 0;
			distance += Math.abs(v1 - v2);
		}
		return distance;
	}

	/**
	 * Compute the Binary Branch Vector for a NBTree. Scan all nodes of the tree
	 * and store Binary Branch of them.
	 */
	private static void computeVector(Map<String, Integer> bbv, NBTree tree) {
		String hashBiB = tree.getBranchString();

		if (!bbv.containsKey(hashBiB))
			bbv.put(hashBiB, 1);
		else {
			int value = bbv.get(hashBiB) + 1;
			bbv.put(hashBiB, value);
		}

		NBTree child = tree.getLeft();
		if (!child.isEmpty())
			computeVector(bbv, child);

		child = tree.getRight();
		if (!child.isEmpty())
			computeVector(bbv, child);
	}
}
